Networks are made up of nodes, and links that connect the nodes to one another. In a computer network, the nodes may include conventional routers, and the links may include the physical wiring that connects the routers and other nodes to one another.
Conventional networks may be made up of customer networks coupled to service provider networks. Each customer network may be managed by that customer within a single customer site. However, to connect multiple customer networks that are geographically dispersed, a service provider network may be used. The service provider network can run between the different customer sites to allow the different customer networks to be interconnected. Additionally, the service provider network may carry traffic from multiple customer networks, allowing the customers to share the facilities of the service provider.
Some customers arrange for their service providers to provide virtual private network connections within the service provider network. A virtual private network connection provides tunneled connections through the service provider network that allows the service provider to provide features to each customer that the customer desires. Such features can include high security, a certain class of service, or other features.
When a router receives a non-virtual private network (VPN) packet, the router receives the destination IP address for the packet, which is unique among destination IP addresses that may be used over the service provider network, and usually is unique among the Internet.
Although the router only uses the destination IP address to determine the next hop router to send the packet, it can be desirable for network analysis to allow the network service provider to identify the entire path that the packet will take through the service provider network. The IP address in a non-VPN packet can also indicate to which customer the packet belongs, enabling analysis by customer for various network measurements.
However, when a router in a service provider network receives a VPN packet in a layer 3 VPN network operated by a service provider, the IP address may not be helpful in determining the ultimate destination of the packet, because the IP address may be an unroutable IP address that is only unique within the customer network, and may not be unique among the various customers of the service provider or the Internet. In order to determine how to route the packet, the router will receive an MPLS label corresponding to the egress PE router, the router at the edge of the provider network that will carry the traffic, that is meaningful only to the router and the router from which the VPN packet was received. However, the MPLS label is not a label for the entire tunnel, it is a label only for the portion of the tunnel between one router and the next hop router. As the packet hops through different routers, the MPLS labels used may change. This makes it difficult to determine at any point in the service provider network the exact path a packet will take because merely knowing the destination IP address and the MPLS label does not uniquely identify the destination of the packet.
The inability to discern the ultimate destination of a VPN-packet can lead to difficulties tracing problems with a provider network or performing capacity planning by the operator of the provider network. Furthermore, without, knowledge of the paths the traffic is taking, it can be difficult to identify the specific customer who will use or has used a particular link or node, and it can be difficult for a provider to perform capacity planning. If a link or node will be brought down for scheduled maintenance, it can be difficult to identify the customers who will be affected.
Retrieving traffic information from the provider edge (“PE”) routers at the edge of the service provider network could make it easier to identify the router from which the provider initially receives the traffic (referred to as an “ingress router), but because there may be a significant number of such PE routers, the retrieval of traffic information from such a large number of PE routers may not only be expensive, but could significantly affect network performance.
What is needed is a system and method that can identify the path, including ingress and egress routers of a layer 3 VPN packet in a service provider network shared by multiple different customer entities and identify links and nodes used by individual customers in such a network without retrieving traffic information from the PE routers, even if the identity of the ingress router is unknown and even if the identity of routers to ports of other routers is not completely available.